/*
 * @lc app=leetcode.cn id=69 lang=cpp
 *
 * [69] x 的平方根
 */

// @lc code=start
class Solution
{
 public:
  int mySqrt(int x)
  {
    // 1.确定二分的边界
    int l = 0, r = x;
    // 2.编写二分的代码框架
    while (l < r)
    {
      int mid = 1 + (long long)r + l >> 1;
      // 3.设计一个check(性质)：见笔记需要满足二段性质
      if (mid <= x / mid)  // 防止溢出
        // 4.判断区间如何更新
        l = mid;
      else
        r = mid - 1;
      // 5.如果更新方式写的是l=mid，r=mid-1,那么就在算mid的时候加上1
    }
    return r;
  }
};
// @lc code=end
